/*
 * ArrayUtils.java Created Aug 29, 2005 by Andrew Butler, PSL
 */
package prisms.util;

import java.lang.reflect.Array;

/**
 * ArrayUtils provides some static methods for manipulating arrays easily when using a tool such as
 * {@link java.util.ArrayList} is inconvenient.
 */
public final class ArrayUtils
{
	/**
	 * Gets the first element in the given array for which the
	 * {@link EqualsChecker#equals(Object, Object)} returns true, or null if this never occurs. The
	 * equals method is called with the element as the first argument and the test parameter as the
	 * second.
	 * 
	 * @param <T> The type of array to get an element of
	 * @param array The array to get the element of
	 * @param test The object to compare the others with. This may be null.
	 * @param checker The checker to determine which element to get
	 * @return The first element in the array for which the
	 *         {@link EqualsChecker#equals(Object, Object)} returns true, or null if this never
	 *         occurs
	 */
	public static <T> T get(T [] array, Object test, EqualsChecker checker)
	{
		for(T el : array)
			if(checker.equals(el, test))
				return el;
		return null;
	}

	/**
	 * Inserts an element into the array--for primitive types
	 * 
	 * @param anArray The array to insert into
	 * @param anElement The element to insert
	 * @param anIndex The index for the new element
	 * @return The new array with all elements of <code>anArray</code>, but with
	 *         <code>anElement</code> inserted at index <code>anIndex</code>
	 */
	public static Object addP(Object anArray, Object anElement, int anIndex)
	{
		Object ret;
		int length;
		if(anArray == null)
		{
			if(anIndex != 0)
				throw new ArrayIndexOutOfBoundsException("Cannot set " + anIndex
					+ " element in a null array");
			ret = Array.newInstance(anElement.getClass(), 1);
			Array.set(ret, 0, anElement);
			return ret;
		}
		else
		{
			length = Array.getLength(anArray);
			ret = Array.newInstance(anArray.getClass().getComponentType(), length + 1);
		}
		System.arraycopy(anArray, 0, ret, 0, anIndex);
		put(ret, anElement, anIndex);
		System.arraycopy(anArray, anIndex, ret, anIndex + 1, length - anIndex);
		return ret;
	}

	/**
	 * Inserts an element into the array
	 * 
	 * @param <T> The type of the object array
	 * @param anArray The array to insert into
	 * @param anElement The element to insert
	 * @param anIndex The index for the new element
	 * @return The new array with all elements of <code>anArray</code>, but with
	 *         <code>anElement</code> inserted at index <code>anIndex</code>
	 */
	public static <T> T [] add(T [] anArray, T anElement, int anIndex)
	{
		T [] ret;
		if(anArray == null)
		{
			if(anIndex != 0)
				throw new ArrayIndexOutOfBoundsException("Cannot set " + anIndex
					+ " element in a null array");
			ret = (T []) Array.newInstance(anElement.getClass(), 1);
			ret[0] = anElement;
			return ret;
		}
		else
			ret = (T []) Array.newInstance(anArray.getClass().getComponentType(),
				anArray.length + 1);
		System.arraycopy(anArray, 0, ret, 0, anIndex);
		put(ret, anElement, anIndex);
		System.arraycopy(anArray, anIndex, ret, anIndex + 1, anArray.length - anIndex);
		return ret;
	}

	/**
	 * @param anArray The array to extend
	 * @param anElement The element to add into <code>anArray</code>
	 * @return A new array of length <code>anArray.length+1</code> whose contents are those of
	 *         <code>anArray</code> followed by <code>anElement</code>
	 */
	public static Object addP(Object anArray, Object anElement)
	{
		int len = anArray == null ? 0 : Array.getLength(anArray);
		return addP(anArray, anElement, len);
	}

	/**
	 * @param <T> The type of the array
	 * @param anArray The array to extend
	 * @param anElement The element to add into <code>anArray</code>
	 * @return A new array of length <code>anArray.length+1</code> whose contents are those of
	 *         <code>anArray</code> followed by <code>anElement</code>
	 */
	public static <T> T [] add(T [] anArray, T anElement)
	{
		int len = anArray == null ? 0 : Array.getLength(anArray);
		return add(anArray, anElement, len);
	}

	/**
	 * Moves an element in an array from one index to another
	 * 
	 * @param <T> The type of the array
	 * @param anArray The array to move an element within
	 * @param from The index of the element to move
	 * @param to The index to move the element to
	 * @return The original array
	 */
	public static <T> T [] move(T [] anArray, int from, int to)
	{
		final T element = anArray[from];
		for(; from < to; from++)
			anArray[from] = anArray[from + 1];
		for(; from > to; from--)
			anArray[from] = anArray[from - 1];
		anArray[to] = element;
		return anArray;
	}

	/**
	 * Moves an element in a primitive array from one index to another
	 * 
	 * @param anArray The array to move an element within
	 * @param from The index of the element to move
	 * @param to The index to move the element to
	 * @return The original array
	 */
	public static Object moveP(Object anArray, int from, int to)
	{
		if(anArray instanceof Object [])
			return move((Object []) anArray, from, to);
		final Object element = Array.get(anArray, from);
		for(; from < to; from++)
			Array.set(anArray, from, Array.get(anArray, from + 1));
		for(; from > to; from--)
			Array.set(anArray, from, Array.get(anArray, from - 1));
		Array.set(anArray, to, element);
		return anArray;
	}

	private static void put(Object array, Object element, int index)
	{
		try
		{
			if(array instanceof Object [])
			{
				try
				{
					((Object []) array)[index] = element;
				} catch(ArrayStoreException e)
				{
					throw new IllegalArgumentException(e.getMessage() + ": "
						+ (element == null ? "null" : element.getClass().getName()) + " into "
						+ array.getClass().getName());
				}
			}
			else
			{
				try
				{
					Array.set(array, index, element);
				} catch(IllegalArgumentException e)
				{
					throw new IllegalArgumentException(e.getMessage() + ": "
						+ (element == null ? "null" : element.getClass().getName()) + " into "
						+ array.getClass().getName(), e);
				}
			}
		} catch(ArrayIndexOutOfBoundsException e)
		{
			throw new ArrayIndexOutOfBoundsException(index + " into " + Array.getLength(array));
		}
	}

	/**
	 * Merges all elements of a set of arrays into a single array with no duplicates. For primitive
	 * types.
	 * 
	 * @param type The type of the result
	 * @param arrays The arrays to merge
	 * @return A new array containing all elements of <code>array1</code> and all elements of
	 *         <code>array2</code> that are not present in <code>array1</code>
	 * @throws NullPointerException If either array is null
	 * @throws ArrayStoreException If elements in the arrays are incompatible with <code>type</code>
	 */
	public static Object mergeInclusiveP(Class<?> type, Object... arrays)
	{
		java.util.LinkedHashSet<Object> set = new java.util.LinkedHashSet<Object>();
		int i, j;
		for(i = 0; i < arrays.length; i++)
		{
			int len = Array.getLength(arrays[i]);
			for(j = 0; j < len; j++)
				set.add(Array.get(arrays[i], j));
		}
		Object ret = Array.newInstance(type, set.size());
		i = 0;
		for(Object el : set)
		{
			put(ret, el, i);
			i++;
		}
		return ret;
	}

	/**
	 * Merges all elements of a set of arrays into a single array with no duplicates.
	 * 
	 * @param <T1> The type of the result
	 * @param <T2> The type of the input arrays
	 * @param type The type of the result
	 * @param arrays The arrays to merge
	 * @return A new array containing all elements of <code>array1</code> and all elements of
	 *         <code>array2</code> that are not present in <code>array1</code>
	 * @throws NullPointerException If either array is null
	 */
	public static <T1, T2 extends T1> T1 [] mergeInclusive(Class<T1> type, T2 []... arrays)
	{
		java.util.LinkedHashSet<T1> set = new java.util.LinkedHashSet<T1>();
		int i, j;
		for(i = 0; i < arrays.length; i++)
		{
			for(j = 0; j < arrays[i].length; j++)
				set.add(arrays[i][j]);
		}
		return set.toArray((T1 []) Array.newInstance(type, set.size()));
	}

	/**
	 * Merges elements found in each of a set of arrays into a single array with no duplicates. For
	 * primitive types.
	 * 
	 * @param type The type of the result
	 * @param arrays The arrays to merge
	 * @return A new array containing all common elements between <code>array1</code> and
	 *         <code>array2</code>
	 * @throws NullPointerException If either array is null
	 * @throws ArrayStoreException If elements in the arrays are incompatible with <code>type</code>
	 */
	public static Object mergeExclusiveP(Class<?> type, Object... arrays)
	{
		if(arrays.length == 0)
			return Array.newInstance(type, 0);
		java.util.ArrayList<Object> retSet = new java.util.ArrayList<Object>();
		int i, j, k;
		int len = Array.getLength(arrays[0]);
		for(j = 0; j < len; j++)
			retSet.add(Array.get(arrays[0], j));
		for(i = 1; i < arrays.length; i++)
		{
			for(j = 0; j < retSet.size(); j++)
			{
				len = Array.getLength(arrays[i]);
				boolean hasEl = false;
				for(k = 0; k < len; k++)
					if(equalsUnordered(retSet.get(j), Array.get(arrays[i], k)))
					{
						hasEl = true;
						break;
					}
				if(!hasEl)
				{
					retSet.remove(j);
					j--;
				}
			}
		}
		Object ret = Array.newInstance(type, retSet.size());
		for(i = 0; i < retSet.size(); i++)
			Array.set(ret, i, retSet.get(i));
		return ret;
	}

	/**
	 * Merges elements found in both of two arrays into a single array with no duplicates.
	 * 
	 * @param <T1> The type of the result
	 * @param <T2> The type of the input arrays
	 * @param type The type of the result
	 * @param arrays The arrays to merge
	 * @return A new array containing all common elements between <code>array1</code> and
	 *         <code>array2</code>
	 * @throws NullPointerException If either array is null
	 */
	public static <T1, T2 extends T1> T1 [] mergeExclusive(Class<T1> type, T2 []... arrays)
	{
		if(arrays.length == 0)
			return (T1 []) Array.newInstance(type, 0);
		java.util.ArrayList<Object> retSet = new java.util.ArrayList<Object>();
		int i, j, k;
		for(j = 0; j < arrays[0].length; j++)
			retSet.add(arrays[0][j]);
		for(i = 1; i < arrays.length; i++)
		{
			for(j = 0; j < retSet.size(); j++)
			{
				boolean hasEl = false;
				for(k = 0; k < arrays[i].length; k++)
					if(equalsUnordered(retSet.get(j), arrays[i][k]))
					{
						hasEl = true;
						break;
					}
				if(!hasEl)
				{
					retSet.remove(j);
					j--;
				}
			}
		}
		return retSet.toArray((T1 []) Array.newInstance(type, retSet.size()));
	}

	/**
	 * Concatenates a series of arrays of any type
	 * 
	 * @param type The type of the arrays
	 * @param arrays The arrays to concatenate
	 * @return An array containing all elements of the arrays
	 */
	public static Object concatP(Class<?> type, Object... arrays)
	{
		if(arrays.length == 0)
			return Array.newInstance(type, 0);
		if(arrays.length == 1)
			return arrays[0];
		int size = 0;
		int [] sizes = new int [arrays.length];
		for(int a = 0; a < arrays.length; a++)
		{
			sizes[a] = Array.getLength(arrays[a]);
			size += sizes[a];
		}
		Object ret = Array.newInstance(type, size);
		int aLen = 0;
		for(int a = 0; a < arrays.length; a++)
		{
			System.arraycopy(arrays[a], 0, ret, aLen, sizes[a]);
			aLen += sizes[a];
		}
		return ret;
	}

	/**
	 * Concatenates a series of arrays of a non-primitive type
	 * 
	 * @param <T> The type of the arrays
	 * @param type The type of the arrays
	 * @param arrays The arrays to concatenate
	 * @return An array containing all elements of the arrays
	 */
	public static <T> T [] concat(Class<T> type, T []... arrays)
	{
		if(arrays.length == 0)
			return (T []) Array.newInstance(type, 0);
		if(arrays.length == 1)
			return arrays[0];
		int size = 0;
		for(int a = 0; a < arrays.length; a++)
		{
			if(arrays[a] != null)
				size += arrays[a].length;
		}
		T [] ret = (T []) Array.newInstance(type, size);
		int aLen = 0;
		for(int a = 0; a < arrays.length; a++)
		{
			if(arrays[a] == null)
				continue;
			System.arraycopy(arrays[a], 0, ret, aLen, arrays[a].length);
			aLen += arrays[a].length;
		}
		return ret;
	}

	/**
	 * @param anArray The array to search
	 * @param anElement The element to search for
	 * @return The first index <code>0&lt;=idx&lt;anArray.length</code> such that
	 *         {@link #equals(Object, Object)} returns true for both <code>anArray[idx]</code> and
	 *         <code>anElement</code>, or -1 if no such index exists
	 */
	public static int indexOf(Object anArray, Object anElement)
	{
		if(anArray instanceof Object [])
		{
			Object [] array2 = (Object []) anArray;
			for(int i = 0; i < array2.length; i++)
			{
				if(equals(array2[i], anElement))
					return i;
			}
			return -1;
		}
		else
		{
			int i, len;
			len = Array.getLength(anArray);
			for(i = 0; i < len; i++)
			{
				if(equals(Array.get(anArray, i), anElement))
					return i;
			}
			return -1;
		}
	}

	/**
	 * Removes the specified object from the array. For primitive types.
	 * 
	 * @param anArray The array to remove an element from
	 * @param anIndex The index of the element to remove
	 * @return A new array with all the elements of <code>anArray</code> except the element at
	 *         <code>anIndex</code>
	 */
	public static Object removeP(Object anArray, int anIndex)
	{
		Object ret;
		int length;
		if(anArray == null)
			return null;
		else
		{
			length = Array.getLength(anArray);
			ret = Array.newInstance(anArray.getClass().getComponentType(), length - 1);
		}
		System.arraycopy(anArray, 0, ret, 0, anIndex);
		System.arraycopy(anArray, anIndex + 1, ret, anIndex, length - anIndex - 1);
		return ret;
	}

	/**
	 * Removes the specified object from the array
	 * 
	 * @param <T> The type of the array
	 * @param anArray The array to remove an element from
	 * @param anIndex The index of the element to remove
	 * @return A new array with all the elements of <code>anArray</code> except the element at
	 *         <code>anIndex</code>
	 */
	public static <T> T [] remove(T [] anArray, int anIndex)
	{
		T [] ret;
		if(anArray == null)
			return null;
		else
		{
			ret = (T []) Array.newInstance(anArray.getClass().getComponentType(),
				anArray.length - 1);
		}
		System.arraycopy(anArray, 0, ret, 0, anIndex);
		System.arraycopy(anArray, anIndex + 1, ret, anIndex, anArray.length - anIndex - 1);
		return ret;
	}

	/**
	 * Removes the specified object from the array
	 * 
	 * @param anArray The array to remove an element from
	 * @param anElement The element to remove
	 * @return A new array with all the elements of <code>anArray</code> except
	 *         <code>anElement</code>
	 */
	public static Object remove(Object anArray, Object anElement)
	{
		int idx = indexOf(anArray, anElement);
		if(idx >= 0)
			return removeP(anArray, idx);
		else
			return anArray;
	}

	/**
	 * Removes the specified object from the array
	 * 
	 * @param <T> The type of the array
	 * @param anArray The array to remove an element from
	 * @param anElement The element to remove
	 * @return A new array with all the elements of <code>anArray</code> except
	 *         <code>anElement</code>
	 */
	public static <T> T [] remove(T [] anArray, T anElement)
	{
		int idx = indexOf(anArray, anElement);
		if(idx >= 0)
			return remove(anArray, idx);
		else
			return anArray;
	}

	/**
	 * Removes all contents of <code>array2</code> from <code>array1</code>. All instances of
	 * <code>array2</code> will also be removed from <code>array1</code>. For primitive types.
	 * 
	 * @param array1 The array to remove elements from
	 * @param array2 The array containing the elements to remove; or the element to remove itself
	 * @return <code>array1</code> missing all the contents of <code>array2</code>
	 */
	public static Object removeAllP(Object array1, Object array2)
	{
		if(array1 == null || array2 == null)
			return array1;
		if(!array1.getClass().isArray())
			return null;
		if(!array2.getClass().isArray())
			array2 = new Object [] {array2};
		else
			array2 = addP(array2, array2);
		java.util.BitSet remove = new java.util.BitSet();
		int len1 = Array.getLength(array1);
		int len2 = Array.getLength(array2);
		int i, j;
		for(i = 0; i < len1; i++)
		{
			for(j = 0; j < len2; j++)
			{
				if(equals(Array.get(array1, i), Array.get(array2, j)))
				{
					remove.set(i);
					break;
				}
			}
		}
		Object ret = Array.newInstance(array1.getClass().getComponentType(), len1
			- remove.cardinality());
		// This copying section might be replaced by a more efficient version
		// using System.arraycopy()--this would be much faster than reflection,
		// especially for large arrays needing only a few elements removed
		for(i = 0, j = 0; i < len1; i++)
		{
			if(!remove.get(i))
			{
				put(ret, Array.get(array1, i), j);
				j++;
			}
		}
		return ret;
	}

	/**
	 * Removes all contents of <code>array2</code> from <code>array1</code>. All instances of
	 * <code>array2</code> will also be removed from <code>array1</code>.
	 * 
	 * @param <T> The type of the array
	 * @param array1 The array to remove elements from
	 * @param array2 The array containing the elements to remove; or the element to remove itself
	 * @return <code>array1</code> missing all the contents of <code>array2</code>
	 */
	public static <T> T [] removeAll(T [] array1, Object array2)
	{
		if(array1 == null || array2 == null)
			return array1;
		if(!array1.getClass().isArray())
			return null;
		if(!array2.getClass().isArray())
			array2 = new Object [] {array2};
		java.util.BitSet remove = new java.util.BitSet();
		int len1 = array1.length;
		int len2 = Array.getLength(array2);
		int i, j;
		for(i = 0; i < len1; i++)
		{
			for(j = 0; j < len2; j++)
			{
				if(equals(array1[i], Array.get(array2, j)))
				{
					remove.set(i);
					break;
				}
			}
		}
		T [] ret = (T []) Array.newInstance(array1.getClass().getComponentType(), len1
			- remove.cardinality());
		// This copying section might be replaced by a more efficient version
		// using System.arraycopy()--this would be much faster than reflection,
		// especially for large arrays needing only a few elements removed
		for(i = 0, j = 0; i < len1; i++)
		{
			if(!remove.get(i))
			{
				ret[j] = array1[i];
				j++;
			}
		}
		return ret;
	}

	/**
	 * Searches an array (possibly primitive) for an element
	 * 
	 * @param anArray The array to search
	 * @param anElement The element to search for
	 * @return True if <code>anArray</code> contains <code>anElement</code>, false otherwise
	 */
	public static boolean containsP(Object anArray, Object anElement)
	{
		if(anArray == null)
			return false;
		if(anArray instanceof Object [])
		{
			Object [] oa = (Object []) anArray;
			for(int i = 0; i < oa.length; i++)
			{
				if(equals(oa[i], anElement))
					return true;
			}
		}
		else
		{
			int len = Array.getLength(anArray);
			for(int i = 0; i < len; i++)
			{
				if(equals(Array.get(anArray, i), anElement))
					return true;
			}
		}
		return false;
	}

	/**
	 * @param <T> The type of the array to search
	 * @param <E> The type of the element to search for
	 * @param anArray The array to search
	 * @param anElement The element to search for
	 * @return True if <code>anArray</code> contains <code>anElement</code>, false otherwise
	 */
	public static <T, E extends T> boolean contains(T [] anArray, E anElement)
	{
		for(int i = 0; i < anArray.length; i++)
		{
			if(equals(anArray[i], anElement))
				return true;
		}
		return false;
	}

	/**
	 * Like {@link #containsP(Object, Object)} but the equality test is by identity instead of the
	 * equals method
	 * 
	 * @param anArray The array to search
	 * @param anElement The element to search for
	 * @return True if <code>anArray</code> contains <code>anElement</code> by identity, false
	 *         otherwise
	 */
	public static boolean containspID(Object anArray, Object anElement)
	{
		if(anArray == null)
			return false;
		if(anArray instanceof Object [])
		{
			Object [] oa = (Object []) anArray;
			for(int i = 0; i < oa.length; i++)
			{
				if(oa[i] == anElement)
					return true;
			}
		}
		else
		{
			int len = Array.getLength(anArray);
			for(int i = 0; i < len; i++)
			{
				if(Array.get(anArray, i) == anElement)
					return true;
			}
		}
		return false;
	}

	/**
	 * Like {@link #contains(Object[], Object)} but the equality test is by identity instead of the
	 * equals method
	 * 
	 * @param <T> The type of the array to search
	 * @param <E> The type of the element to search for
	 * @param anArray The array to search
	 * @param anElement The element to search for
	 * @return True if <code>anArray</code> contains <code>anElement</code> by identity, false
	 *         otherwise
	 */
	public static <T, E extends T> boolean containsID(T [] anArray, E anElement)
	{
		for(int i = 0; i < anArray.length; i++)
		{
			if(anArray[i] == anElement)
				return true;
		}
		return false;
	}

	/**
	 * A utility version of equals that allows comparison of null objects and arrays. WARNING: Does
	 * not account for an array that contains a reference to itself, directly or indirectly
	 * 
	 * @param o1 The first object to compare
	 * @param o2 The second object to compare
	 * @return true if <code>o1</code> and <code>o2</code> are arrays and their elements are
	 *         equivalent or if either <code>o1==null && o2==null</code> or
	 *         <code>o1.equals(o2)</code>, false otherwise
	 */
	public static boolean equals(Object o1, Object o2)
	{
		if(o1 == null)
			return o2 == null;
		if(o2 == null)
			return false;
		if(o1 instanceof Object [] && o2 instanceof Object [])
			return equals((Object []) o1, (Object []) o2);
		if(o1.getClass().isArray() && o2.getClass().isArray())
		{
			if(!o1.getClass().equals(o2.getClass()))
				return false;
			int len = Array.getLength(o1);
			if(len != Array.getLength(o2))
				return false;
			for(int i = 0; i < len; i++)
			{
				if(!equals(Array.get(o1, i), Array.get(o2, i)))
					return false;
			}
			return true;
		}
		return o1.equals(o2);
	}

	private static boolean equals(Object [] o1, Object [] o2)
	{
		if(o1 == null)
			return o2 == null;
		if(o2 == null)
			return false;
		if(!o1.getClass().equals(o2.getClass()))
			return false;
		if(o1.length != o2.length)
			return false;
		for(int i = 0; i < o1.length; i++)
		{
			if(!equals(o1[i], o2[i]))
				return false;
		}
		return true;
	}

	/**
	 * Like {@link #equals(Object, Object)}, but compares arrays without regard to order
	 * 
	 * @param o1 The first object to compare
	 * @param o2 The second object to compare
	 * @return true if <code>o1</code> and <code>o2</code> are arrays and their elements are
	 *         equivalent or if either <code>o1==null && o2==null</code> or
	 *         <code>o1.equals(o2)</code>, false otherwise
	 */
	public static boolean equalsUnordered(Object o1, Object o2)
	{
		return equalsUnordered(o1, o2, new EqualsChecker()
		{
			public boolean equals(Object o3, Object o4)
			{
				if(o3 == null)
					return o4 == null;
				if(o4 == null)
					return false;
				if(!o3.getClass().isArray())
				{
					if(o4.getClass().isArray())
						return false;
					return o3.equals(o4);
				}
				else if(!o4.getClass().isArray())
					return false;
				return equalsUnordered(o3, o4);
			}
		});
	}

	/**
	 * Checks two values for equality
	 */
	public static interface EqualsChecker
	{
		/**
		 * Checks two values for equality
		 * 
		 * @param o1 The first value to check
		 * @param o2 The second value to check
		 * @return Whether the two values are equal
		 */
		boolean equals(Object o1, Object o2);
	}

	/**
	 * Like {@link #equals(Object, Object)}, but compares arrays without regard to order and uses an
	 * independent checker to check for equality of elements
	 * 
	 * @param o1 The first object to compare
	 * @param o2 The second object to compare
	 * @param checker The checker to check elements for equality
	 * @return true if <code>o1</code> and <code>o2</code> are arrays and their elements are
	 *         equivalent or if either <code>o1==null && o2==null</code> or
	 *         <code>o1.equals(o2)</code>, false otherwise
	 */
	public static boolean equalsUnordered(Object o1, Object o2, EqualsChecker checker)
	{
		if(o1 == null)
			return o2 == null;
		if(o2 == null)
			return false;
		if(o1 instanceof Object [] && o2 instanceof Object [])
			return equalsUnordered((Object []) o1, (Object []) o2, checker);
		if(o1.getClass().isArray() && o2.getClass().isArray())
		{
			if(!o1.getClass().equals(o2.getClass()))
				return false;
			int len = Array.getLength(o1);
			if(len != Array.getLength(o2))
				return false;
			if(len == 0)
				return true;
			long [] bs = new long [(len - 1) / 64 + 1];
			long mask;
			int i, j, bsIdx;
			o1Loop: for(i = 0; i < len; i++)
			{
				mask = 0;
				for(j = 0; j < len; j++)
				{
					bsIdx = j / 64;
					if(mask == 0)
						mask = 0x8000000000000000L;
					if((bs[bsIdx] & mask) == 0
						&& checker.equals(Array.get(o1, i), Array.get(o2, j)))
					{
						bs[bsIdx] |= mask;
						continue o1Loop;
					}
					mask >>>= 1;
				}
				return false;
			}
			return true;
		}
		return checker.equals(o1, o2);
	}

	private static boolean equalsUnordered(Object [] o1, Object [] o2, EqualsChecker checker)
	{
		if(o1 == null)
			return o2 == null;
		if(o2 == null)
			return false;
		if(o1.length != o2.length)
			return false;
		if(o1.length == 0)
			return true;
		long [] bs = new long [(o2.length - 1) / 64 + 1];
		long mask;
		int i, j, bsIdx;
		o1Loop: for(i = 0; i < o1.length; i++)
		{
			mask = 0;
			for(j = 0; j < o2.length; j++)
			{
				bsIdx = j / 64;
				if(mask == 0)
					mask = 0x8000000000000000L;
				if((bs[bsIdx] & mask) == 0 && checker.equals(o1[i], o2[j]))
				{
					bs[bsIdx] |= mask;
					continue o1Loop;
				}
				mask >>>= 1;
			}
			return false;
		}
		return true;
	}

	/**
	 * A compliment to the {@link #equals(Object, Object)} method, this method returns a hashcode
	 * for <code>array</code> such that it is consistent with the equals contract for the
	 * {@link Object#equals(Object)} method, represented by the {@link #equals(Object, Object)}
	 * method.
	 * 
	 * @param array The array to get a hashcode for
	 * @return A hashcode based on <code>array</code> and its contents, if any
	 */
	public static int hashCode(Object array)
	{
		if(array == null)
			return 0;
		if(!array.getClass().isArray())
			return array.hashCode();
		int ret = array.getClass().getComponentType().hashCode();
		int len = Array.getLength(array);
		for(int i = 0; i < len; i++)
		{
			ret *= hashCode(Array.get(array, i));
			ret += 29;
		}
		return ret;
	}

	/**
	 * A utility method for printing out the contents of an array (not deeply)
	 * 
	 * @param array The array to print
	 * @return A String containing the representation of the contents of <code>array</code>
	 */
	public static String toString(Object array)
	{
		if(array == null)
			return "" + null;
		else if(array instanceof Object [])
		{
			Object [] oa = (Object []) array;
			StringBuffer ret = new StringBuffer("[");
			for(int i = 0; i < oa.length; i++)
			{
				ret.append(toString(oa[i]));
				if(i < oa.length - 1)
					ret.append(", ");
			}
			ret.append("]");
			return ret.toString();
		}
		else if(array.getClass().isArray())
		{
			StringBuffer ret = new StringBuffer("[");
			int len = Array.getLength(array);
			for(int i = 0; i < len; i++)
			{
				ret.append(Array.get(array, i));
				if(i < len - 1)
					ret.append(", ");
			}
			ret.append("]");
			return ret.toString();
		}
		else
			return array.toString();
	}

	/**
	 * Replaces <code>toReplace</code> with <code>replacement</code> in <code>array</code> one time
	 * at the most
	 * 
	 * @param array The array to search and replace in
	 * @param toReplace The object to replace
	 * @param replacement The object to replace <code>toReplace</code> with the first time it is
	 *        found
	 * @return The index where <code>toReplace</code> was found and replaced, or -1 if it was not
	 *         found in <code>array</code>
	 */
	public static int replaceOnce(Object array, Object toReplace, Object replacement)
	{
		if(array instanceof Object [])
		{
			Object [] array2 = (Object []) array;
			for(int i = 0; i < array2.length; i++)
			{
				if(equals(array2[i], toReplace))
				{
					array2[i] = replacement;
					return i;
				}
			}
			return -1;
		}
		else
		{
			int i, len;
			len = Array.getLength(array);
			for(i = 0; i < len; i++)
			{
				if(equals(Array.get(array, i), toReplace))
				{
					put(array, replacement, i);
					return i;
				}
			}
			return -1;
		}
	}

	/**
	 * Replaces <code>toReplace</code> with <code>replacement</code> in <code>array</code> as many
	 * times as it occurs
	 * 
	 * @param array The array to search and replace in
	 * @param toReplace The object to replace
	 * @param replacement The object to replace <code>toReplace</code> with each time it is found
	 * @return The number of times <code>toReplace</code> was found and replaced
	 */
	public static int replaceAll(Object array, Object toReplace, Object replacement)
	{
		int count = 0;
		if(array instanceof Object [])
		{
			Object [] array2 = (Object []) array;
			for(int i = 0; i < array2.length; i++)
			{
				if(equals(array2[i], toReplace))
				{
					array2[i] = replacement;
					count++;
				}
			}
		}
		else
		{
			int i, len;
			len = Array.getLength(array);
			for(i = 0; i < len; i++)
			{
				if(equals(Array.get(array, i), toReplace))
				{
					put(array, replacement, i);
					count++;
				}
			}
		}
		return count;
	}

	/**
	 * Gets the elements that the two arrays have in common. Elements are retrieved from the first
	 * array.
	 * 
	 * @param <T> The type of the first array and the return array
	 * @param <T2> The type of the second array
	 * @param array1 The first array
	 * @param array2 The second array
	 * @return The elements in <code>array1</code> that occur at least once in <code>array2</code>
	 */
	public static <T, T2 extends T> T [] commonElements(T [] array1, T2 [] array2)
	{
		int count = 0;
		if(array1 == null || array2 == null)
			return (T []) Array.newInstance(array1.getClass().getComponentType(), 0);
		int i, j;
		for(i = 0; i < array1.length; i++)
			for(j = 0; j < array2.length; j++)
				if(equals(array1[i], array2[j]))
				{
					count++;
					break;
				}
		T [] ret = (T []) Array.newInstance(array1.getClass().getComponentType(), count);
		count = 0;
		for(i = 0; i < array1.length; i++)
			for(j = 0; j < array2.length; j++)
				if(equals(array1[i], array2[j]))
				{
					ret[count] = array1[i];
					count++;
					break;
				}
		return ret;
	}

	/**
	 * Gets the elements that the two arrays have in common. Elements are retrieved from the first
	 * array.
	 * 
	 * @param array1 The first array
	 * @param array2 The second array
	 * @return The elements in <code>array1</code> that occur at least once in <code>array2</code>
	 */
	public static Object [] commonElementsP(Object array1, Object array2)
	{
		int count = 0;
		if(array1 == null || array2 == null)
			return new Object [0];
		if(!array1.getClass().isArray() || array2.getClass().isArray())
			return new Object [0];
		int len1 = Array.getLength(array1);
		int len2 = Array.getLength(array2);
		int i, j;
		for(i = 0; i < len1; i++)
			for(j = 0; j < len2; j++)
				if(equals(Array.get(array1, i), Array.get(array2, j)))
				{
					count++;
					break;
				}
		Object [] ret = new Object [count];
		count = 0;
		for(i = 0; i < len1; i++)
			for(j = 0; j < len2; j++)
				if(equals(Array.get(array1, i), Array.get(array2, j)))
				{
					ret[count] = Array.get(array1, i);
					count++;
					break;
				}
		return ret;
	}

	/**
	 * Gets the elements that are in array1, but not array 2.
	 * 
	 * @param array1 The first array
	 * @param array2 The second array
	 * @return The elements in <code>array1</code> that do not occur in <code>array2</code>
	 */
	public static Object [] removedElements(Object array1, Object array2)
	{
		int count = 0;
		if(array1 == null || array2 == null)
			return new Object [0];
		if(!array1.getClass().isArray() || array2.getClass().isArray())
			return new Object [0];
		int len1 = Array.getLength(array1);
		int len2 = Array.getLength(array2);
		int i, j;
		for(i = 0; i < len1; i++)
		{
			count++;
			for(j = 0; j < len2; j++)
			{
				if(equals(Array.get(array1, i), Array.get(array2, j)))
				{
					count--;
					break;
				}
			}
		}
		Object [] ret = new Object [count];
		count = 0;
		for(i = 0; i < len1; i++)
		{
			count++;
			for(j = 0; j < len2; j++)
			{
				if(equals(Array.get(array1, i), Array.get(array2, j)))
				{
					count--;
					break;
				}
				ret[count] = Array.get(array1, i);
			}
		}
		return ret;
	}

	/**
	 * Gets the elements that are in array2, but not array 1.
	 * 
	 * @param array1 The first array
	 * @param array2 The second array
	 * @return The elements in <code>array2</code> that do not occur in <code>array1</code>
	 */
	public static Object [] addedElements(Object array1, Object array2)
	{
		int count = 0;
		if(array1 == null || array2 == null)
			return new Object [0];
		if(!array1.getClass().isArray() || array2.getClass().isArray())
			return new Object [0];
		int len1 = Array.getLength(array1);
		int len2 = Array.getLength(array2);
		int i, j;
		for(i = 0; i < len1; i++)
		{
			count++;
			for(j = 0; j < len2; j++)
			{
				if(equals(Array.get(array2, i), Array.get(array1, j)))
				{
					count--;
					break;
				}
			}
		}
		Object [] ret = new Object [count];
		count = 0;
		for(i = 0; i < len1; i++)
		{
			count++;
			for(j = 0; j < len2; j++)
			{
				if(equals(Array.get(array2, i), Array.get(array1, j)))
				{
					count--;
					break;
				}
				ret[count] = Array.get(array2, i);
			}
		}
		return ret;
	}

	/**
	 * Reverses the order of an array
	 * 
	 * @param <T> The type of the array to reverse
	 * @param array The array to reverse
	 * @return The reversed array, same as the original reference
	 */
	public static <T> T [] reverse(T [] array)
	{
		T temp;
		final int aLen = array.length - 1;
		for(int i = 0; i < array.length / 2; i++)
		{
			temp = array[i];
			array[i] = array[aLen - i];
			array[aLen - i] = temp;
		}
		return array;
	}

	/**
	 * Reverses the order of an array. Similar to {@link #reverse(Object[])} but works for primitive
	 * arrays as well.
	 * 
	 * @param array The array to reverse
	 * @return The reversed array, same as the original reference
	 */
	public static Object reverseP(Object array)
	{
		if(array instanceof Object [])
			return reverse((Object []) array);
		Object temp;
		final int aLen = Array.getLength(array);
		for(int i = 0; i < aLen / 2; i++)
		{
			temp = Array.get(array, i);
			put(array, Array.get(array, aLen - i - 1), i);
			put(array, temp, aLen - i - 1);
		}
		return array;
	}

	/**
	 * @see DifferenceListenerE
	 * 
	 * @param <T1> The type of the original array
	 * @param <T2> The type of the modifying array
	 */
	public static interface DifferenceListener<T1, T2> extends
		DifferenceListenerE<T1, T2, RuntimeException>
	{
		/**
		 * @see prisms.util.ArrayUtils.DifferenceListenerE#identity(java.lang.Object,
		 *      java.lang.Object)
		 */
		boolean identity(T1 o1, T2 o2);

		/**
		 * @see prisms.util.ArrayUtils.DifferenceListenerE#added(java.lang.Object, int, int)
		 */
		T1 added(T2 o, int mIdx, int retIdx);

		/**
		 * @see prisms.util.ArrayUtils.DifferenceListenerE#removed(java.lang.Object, int, int, int)
		 */
		T1 removed(T1 o, int oIdx, int incMod, int retIdx);

		/**
		 * @see prisms.util.ArrayUtils.DifferenceListenerE#set(java.lang.Object, int, int,
		 *      java.lang.Object, int, int)
		 */
		T1 set(T1 o1, int idx1, int incMod, T2 o2, int idx2, int retIdx);
	}

	/**
	 * <p>
	 * This listener contains all information needed to reconcile two arrays using the
	 * {@link ArrayUtils#adjust(Object[], Object[], prisms.util.ArrayUtils.DifferenceListenerE)}
	 * method.
	 * </p>
	 * 
	 * <p>
	 * There are many different indices that may or may not be relevant to a particular listener:
	 * <ul>
	 * <li><b>oIdx:</b> The index of the element in the original array</li>
	 * <li><b>incMod:</b> The index of the element in a copy of the original array that has been
	 * modified incrementally for each add, remove, and reorder operation</li>
	 * <li><b>mIdx:</b> The index of the element in the modifier array</li>
	 * <li><b>retIdx:</b> The index that the returned element (if not null) will be at in the result
	 * array</li>
	 * </ul>
	 * oIdx and mIdx are self-explanatory. incMod and retIdx are useful for listeners that modify an
	 * external ordered set incrementally with each listener method invocation.
	 * </p>
	 * 
	 * <p>
	 * <b>An Example</b><br /> Suppose there is a list, <b>L</b>, whose data can only be modified
	 * incrementally by the methods add(value, index), remove(index), and move(fromIndex, toIndex),
	 * but can be accessed in batch by the getData method, which returns an array of all data in the
	 * list. Suppose the list needs to be modified to represent a new arbitrary set of data,
	 * <b>d</b>. <b>d</b> may or may not contain elements represented in <b>L</b>. These elements,
	 * if present, may be in different order and new items not present in <b>L</b> may be present in
	 * <b>d</b>. To modify <b>L</b> to represent the data in <b>d</b> in the correct order, the
	 * {@link ArrayUtils#adjust(Object[], Object[], DifferenceListenerE)} method should be called
	 * with <b>L</b>.getData(), <b>d</b>, and a listener whose methods perform the following
	 * operations:
	 * <ul>
	 * <li>{@link #identity(Object, Object)}: Tests the two elements to see if the item from
	 * <b>L</b> represents the item in <b>d</b>, possibly by simply calling
	 * {@link Object#equals(Object)}</li>
	 * <li>{@link #added(Object, int, int)}: Invokes <b>L</b>.add(o2, retIdx).</li>
	 * <li>{@link #removed(Object, int, int, int)}: Invokes <b>L</b>.remove(incMod). Using incMod
	 * accounts for any previous modifications that may have been performed on the list from the
	 * listener.</li>
	 * <li>{@link #set(Object, int, int, Object, int, int)}: Invokes <b>L</b>.move(incMod, retIdx).
	 * This again accounts for all previous changes to the list and moves the element to the index
	 * intended by the adjust method.</li>
	 * </ul>
	 * The end result of this invocation will be that <b>L</b> contains all the data in <b>d</b>,
	 * only the data in <b>d</b>, and is ordered identically to <b>d</b>. The returned array may be
	 * ignored.
	 * </p>
	 * 
	 * <p>
	 * <b>Alternate Operation:</b><br />
	 * <ul>
	 * <li>If it is intended that the modification operation should only add data to <b>L</b>, the
	 * remove method may do nothing and return o. The return value will cause the adjust method to
	 * update future indexes, assuming that the value is kept and not removed.</li>
	 * <li>If order is not important or no move(fromIndex, toIndex) method exists, the set method
	 * may do nothing and return o1. This will have no effect on the result of the operation other
	 * than leaving the items originally in <b>L</b> (those that were also present in <b>d</b>) in
	 * their original order.</li>
	 * <li>Other permutations may exist depending on the business logic used by the listener.</li>
	 * </ul>
	 * </p>
	 * 
	 * <p>
	 * The listener is entirely free to choose whether items are added or removed from the original
	 * array and its representations by modifying whether the return value from those methods is
	 * null. The adjust method does not care what is returned from the add/remove/set methods except
	 * whether the value is null. The listener is free to perform index moving operations or not.
	 * This method will never cause an index out of bounds error assuming the related data sets are
	 * not modified by anything other than the listener and the data in the arrays passed into the
	 * adjust method do not change.
	 * </p>
	 * 
	 * @param <T1> The type of the original array
	 * @param <T2> The type of the modifying array
	 * @param <E> The type of exception that may be thrown
	 */
	public static interface DifferenceListenerE<T1, T2, E extends Throwable>
	{
		/**
		 * Tests the identity of an item from each of the two sets. This method should return true
		 * if one item is a representation of the other or both are a representation of the same
		 * piece of data.
		 * 
		 * @param o1 The object from the first set
		 * @param o2 The object from the second set
		 * @return Whether the two objects are fundamentally equivalent
		 * @throws E If an error occurs in this method
		 */
		boolean identity(T1 o1, T2 o2) throws E;

		/**
		 * Called when a value is found in the second set that is not present in the first set
		 * 
		 * @param o The unmatched object
		 * @param mIdx The index in the second array where the unmatched object was found
		 * @param retIdx The index that the new element will be inserted into the final array
		 * @return The new T1-type element to insert into the return array, or null if the new
		 *         element is not to be inserted
		 * @throws E If an error occurs in this method
		 */
		T1 added(T2 o, int mIdx, int retIdx) throws E;

		/**
		 * Called when a value is found in the first set that is not present in the second set
		 * 
		 * @param o The unmatched object
		 * @param oIdx The index in the first array where the unmatched object was found
		 * @param incMod The index where the unmatched element would occur the incrementally
		 *        modified original array
		 * @param retIdx The index in the final array where the replacement will be located if a
		 *        non-null value is returned
		 * @return null if the original object is to be removed, otherwise its replacement
		 * @throws E If an error occurs in this method
		 */
		T1 removed(T1 o, int oIdx, int incMod, int retIdx) throws E;

		/**
		 * Called when elements in the two arrays match
		 * 
		 * @param o1 The element in the first array
		 * @param idx1 The index of the element in the first array
		 * @param incMod The index where the element in the original array would occur the
		 *        incrementally modified original array
		 * @param o2 The element in the second array
		 * @param idx2 The index of the element in the second array
		 * @param retIdx The index of the returned element in the final array
		 * @return The element to be inserted in the final array, or null if the element is to be
		 *         removed
		 * @throws E If an error occurs in this method
		 */
		T1 set(T1 o1, int idx1, int incMod, T2 o2, int idx2, int retIdx) throws E;
	}

	/**
	 * <p>
	 * Reconciles differences between two ordered sets of objects. Allows a programmer highly
	 * customized control between two different representations of a data set. The arrays are
	 * compared and the listener is notified when any differences are encountered, allowing it to
	 * determine the composition of the returned array and/or perform well-defined operations
	 * represented by the differences or similarities.
	 * </p>
	 * 
	 * @param <T1> The type of the original array
	 * @param <T2> The type of the modifying array
	 * @param <E> The type of exception that may be thrown
	 * @param original The original array
	 * @param modifier The modifying array
	 * @param dl The listener to determine how to deal with differences between the two arrays
	 * @return A final array that is the result of applying select changes between the original and
	 *         the modifying arrays
	 * @throws E If the {@link DifferenceListenerE} throws an exception
	 */
	public static <T1, T2, E extends Throwable> T1 [] adjust(T1 [] original, T2 [] modifier,
		DifferenceListenerE<T1, T2, E> dl) throws E
	{
		int [] oMappings = new int [original.length];
		int [] mMappings = new int [modifier.length];
		int o, m, r;
		for(m = 0; m < mMappings.length; m++)
			mMappings[m] = -1;
		r = original.length + modifier.length;
		boolean crossMapping = false;
		for(o = 0; o < original.length; o++)
		{
			oMappings[o] = -1;
			for(m = 0; m < modifier.length; m++)
			{
				if(mMappings[m] >= 0)
					continue;
				if(dl.identity(original[o], modifier[m]))
				{
					crossMapping = true;
					oMappings[o] = m;
					mMappings[m] = o;
					r--;
					break;
				}
			}
		}
		Object [] ret = new Object [r];
		int [] incMods = new int [original.length];
		for(int i = 0; i < incMods.length; i++)
			incMods[i] = i;
		r = 0;
		o = 0;
		m = 0;
		if(crossMapping)
		{
			/* If there are items that match, remove the items in the original that occur before
			 * the first match */
			for(; o < original.length && oMappings[o] < 0; o++)
			{
				ret[r] = dl.removed(original[o], o, incMods[o], r);
				if(ret[r] != null)
					r++;
				else
				{ // Adjust the incremental modification indexes
					for(int i = o + 1; i < incMods.length; i++)
						incMods[i]--;
				}
			}
		}
		else
		{
			/* If there were no matches, we want to remove the original items before the modifiers */
			for(o = 0; o < original.length; o++)
			{
				ret[r] = dl.removed(original[o], o, incMods[o], r);
				if(ret[r] != null)
					r++;
				else
				{
					for(int i = o + 1; i < incMods.length; i++)
						incMods[i]--;
				}
			}
		}
		for(m = 0; m < modifier.length; m++)
		{
			/* Add or set each modifier
			 */
			o = mMappings[m];
			if(o >= 0)
			{
				ret[r] = dl.set(original[o], o, incMods[o], modifier[m], m, r);
				if(ret[r] != null)
				{
					// Adjust the incremental modification indexes
					int incMod = incMods[o];
					if(r > incMod)
					{ // Element moved forward--decrement incMods up to the new index
						for(int i = 0; i < incMods.length; i++)
							if(incMods[i] >= incMod && incMods[i] <= r)
								incMods[i]--;
					}
					else if(r < incMod)
					{ // Element moved backward--increment incMods up to the original index
						for(int i = 0; i < incMods.length; i++)
							if(incMods[i] >= r && incMods[i] < incMod)
								incMods[i]++;
					}
					r++;
				}
				else
				{
					for(int i = 0; i < incMods.length; i++)
						if(incMods[i] >= r)
							incMods[i]--;
				}
			}
			else
			{
				ret[r] = dl.added(modifier[m], m, r);
				if(ret[r] != null)
				{
					r++;
					// Adjust the incremental modification indexes
					for(int i = 0; i < incMods.length; i++)
					{
						if(incMods[i] >= r)
							incMods[i]++;
					}
				}
			}
			if(o >= 0)
			{
				/* After each modifier, remove the originals that occur before the next match */
				for(o++; o < original.length && oMappings[o] < 0; o++)
				{
					ret[r] = dl.removed(original[o], o, incMods[o], r);
					if(ret[r] != null)
						r++;
					else
					{ // Adjust the incremental modification indexes
						for(int i = o + 1; i < incMods.length; i++)
							incMods[i]--;
					}
				}
			}
		}

		T1 [] actualRet = (T1 []) Array.newInstance(original.getClass().getComponentType(), r);
		System.arraycopy(ret, 0, actualRet, 0, r);
		return actualRet;
	}

	/**
	 * A listener used for {@link #sort(Object [], SortListener)}
	 * 
	 * @param <T> The type of object to sort
	 */
	public static interface SortListener<T> extends java.util.Comparator<T>
	{
		/**
		 * Called just <u>after</u> two elements are swapped.
		 * 
		 * @param o1 The first element being moved
		 * @param idx1 The index (in the pre-swap array) of the first element
		 * @param o2 The second element being moved
		 * @param idx2 The index (in the pre-swap array) of the second element
		 */
		void swapped(T o1, int idx1, T o2, int idx2);
	}

	/**
	 * Sorts an array, allowing for complex operations during the sort, such as sorting arrays in
	 * parallel.
	 * 
	 * This is an implementation of selection sort. Selection sort is used because although it may
	 * perform many more comparison operations than other methods, there is no other method that
	 * performs fewer swaps. It is anticipated that this algorithm will be used most often in the
	 * case that multiple operations must take place during a swap, while comparison should be
	 * fairly quick.
	 * 
	 * @param <T> The type of the array to sort
	 * @param array The array to sort
	 * @param listener The listener to use for comparisons and to notify of swapping
	 */
	public static <T> void sort(T [] array, SortListener<T> listener)
	{
		for(int i = 0; i < array.length - 1; i++)
		{
			int min = findMin(array, i, listener);
			if(min != i)
			{
				T ta = array[i];
				T tb = array[min];
				array[i] = tb;
				array[min] = ta;
				listener.swapped(ta, i, tb, min);
			}
		}
	}

	private static <T> int findMin(T [] array, int start, SortListener<T> listener)
	{
		int minIdx = start;
		for(int i = start + 1; i < array.length; i++)
			if(listener.compare(array[i], array[minIdx]) < 0)
				minIdx = i;
		return minIdx;
	}

	/**
	 * Represents some statistical information calculated on a set of float data
	 */
	public static class ArrayStatistics
	{
		/**
		 * The smallest non-NaN, non-infinite datum encountered by this statistics set
		 */
		public float min;

		/**
		 * The largest non-NaN, non-infinite datum encountered by this statistics set
		 */
		public float max;

		/**
		 * The number of NaN data encountered by this statistics set
		 */
		public int naNCount;

		/**
		 * The number of +Inf data encountered by this statistics set
		 */
		public int posInfCount;

		/**
		 * The number of -Inf data encountered by this statistics set
		 */
		public int negInfCount;

		/**
		 * The number of non-NaN, non-infinite data encountered by this statistics set
		 */
		public int validCount;

		/**
		 * The mean value of all non-NaN, non-infinite data encountered by this statistics set
		 */
		public float mean;

		/**
		 * A running data measure that allows the standard deviation of all non-NaN, non-infinite
		 * data encountered by this statistics set
		 */
		private float q;

		/**
		 * Creates an ArrayStatistics set
		 */
		public ArrayStatistics()
		{
			min = Float.MAX_VALUE;
			max = Float.MIN_VALUE;
			mean = 0;
			q = Float.NaN;
			validCount = 0;
			naNCount = 0;
			posInfCount = 0;
			negInfCount = 0;
		}

		/**
		 * Adds a value to this statistics set
		 * 
		 * @param value The value to analyze
		 */
		public void inputValue(float value)
		{
			if(Float.isNaN(value))
				naNCount++;
			else if(Float.isInfinite(value))
			{
				if(value > 0)
					posInfCount++;
				else
					negInfCount++;
			}
			else if(validCount == 0)
			{
				mean = value;
				q = 0;
				validCount++;
			}
			else
			{
				if(value < min)
					min = value;
				if(value > max)
					max = value;
				q = q + (validCount * (mean - value) * (mean - value)) / (validCount + 1);
				validCount++;
				mean = mean + (value - mean) / validCount;
			}
		}

		/**
		 * @return The standard deviation of all non-NaN, non-infinite data encountered by this
		 *         statistics set
		 */
		public float getSigma()
		{
			return (float) Math.sqrt(q / (validCount - 1));
		}

		/**
		 * @return The total number of data encountered by this statistics set
		 */
		public int getTotalCount()
		{
			return validCount + naNCount + posInfCount + negInfCount;
		}

		public String toString()
		{
			StringBuilder ret = new StringBuilder();
			ret.append(getTotalCount());
			ret.append(" values ranged ");
			ret.append(min);
			ret.append(" to ");
			ret.append(max);
			ret.append("; mean=");
			ret.append(mean);
			ret.append(", st.dev.=");
			ret.append(getSigma());
			ret.append("; ");
			ret.append(naNCount);
			ret.append("NaN, ");
			ret.append(posInfCount);
			ret.append("+Inf, ");
			ret.append(negInfCount);
			ret.append("-Inf");
			return ret.toString();
		}
	}

	/**
	 * Performs a simple statistical analysis of an array of floats
	 * 
	 * @param array An n-dimensional array of floats
	 * @param stats The ArrayStatistics object to populate, or null to create a new one
	 * @return The statistics object
	 */
	public static ArrayStatistics getStatistics(Object array, ArrayStatistics stats)
	{
		if(array == null)
			return null;
		if(stats == null)
			stats = new ArrayStatistics();
		if(array instanceof Object [])
		{
			for(Object subArray : (Object []) array)
				getStatistics(subArray, stats);
			return stats;
		}
		if(!(array instanceof float []))
			throw new IllegalArgumentException("Cannot statistically analyze a "
				+ array.getClass().getName());
		for(float f : (float []) array)
			stats.inputValue(f);
		return stats;
	}
}
